﻿// 1326. 灌溉花园的最少水龙头数目.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;
/*
https://leetcode.cn/problems/minimum-number-of-taps-to-open-to-water-a-garden/

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。
花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。
给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：
如果打开点 i 处的水龙头，可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。
请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。

示例 1：
输入：n = 5, ranges = [3,4,1,1,0,0]
输出：1
解释：
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

示例 2：
输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。

提示：
1 <= n <= 104
ranges.length == n + 1
0 <= ranges[i] <= 100
*/


class Solution {
public:
    struct SEG {
        int l, r;
    }segs[10010];

    static bool cmp(const struct SEG& a, const struct SEG& b) {
        if (a.l < b.l) return true;
        else if (a.l ==  b.l) return a.r > b.r;

        return false;
    }

    int minTaps(int n, vector<int>& ranges) {
        for (int i = 0; i <= n; i++) {
            segs[i].l = i - ranges[i]; segs[i].l = max(segs[i].l, 0);
            segs[i].r = i + ranges[i]; segs[i].r = min(segs[i].r, n);
        }
        sort(segs,segs+n+1,cmp);
        //贪心选择
       
        if (segs[0].l > 0) return -1;
        int ans = 1; int idx = 1;
       int r = segs[0].r; 

       while (idx <= n) {
           int checkR = r; int start = idx;
           while (idx <= n && segs[idx].l <= r) {
               checkR = max(checkR, segs[idx].r);
               idx++;
           }
           if (idx == start) break;
           if (checkR > r) {
                r = checkR; ans++;
            }
        }

        if (r >= n) return ans;
        return -1;
    }
};


int main()
{
    Solution s;
    vector<int> v{ 3 ,4,1,1,0,0 };
    s.minTaps(5,v);
}

 